package lc322;

//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
//
// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
//
// 你可以认为每种硬币的数量是无限的。
//
//
//
// 示例 1：
//
//
//输入：coins = [1, 2, 5], amount = 11
//输出：3
//解释：11 = 5 + 5 + 1
//
// 示例 2：
//
//
//输入：coins = [2], amount = 3
//输出：-1
//
// 示例 3：
//
//
//输入：coins = [1], amount = 0
//输出：0
//
//
// 示例 4：
//
//
//输入：coins = [1], amount = 1
//输出：1
//
//
// 示例 5：
//
//
//输入：coins = [1], amount = 2
//输出：2
//
//
//
//
// 提示：
//
//
// 1 <= coins.length <= 12
// 1 <= coins[i] <= 2³¹ - 1
// 0 <= amount <= 10⁴
//
// Related Topics 广度优先搜索 数组 动态规划 👍 1545 👎 0

import java.util.Arrays;

/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 * time:O()
 * space:O()
 * spend: 15m
 */
class Solution {

    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        // 记录从0开始到amount的所有结果
        int[] memo = new int[amount + 1];
        // 填充一个永远不到达到的数字，必须大于amount，不建议int max，因为有可能溢出导致结果异常
        Arrays.fill(memo, amount + 1);
        memo[0] = 0;
        // 从1开始
        for(int cur = 1; cur <= amount; cur++){
            for(int coin: coins){
                // 当前金额小于于当前硬币，那就不用运算了
                if(cur - coin >= 0){
                    // 当前最少是在上一个结果的基础上和当前结果进行运算，取最小的值，
                    // [1,2,5]当cur为1的时候，则memo[1]为4, memo[cur - coin]+1为1，则amount 为1的时候，答案是1，也就是1个1
                    // [1,2,5]当cur为2的时候，分为1和2硬币能计算
                    // 先算硬币1，memo[2] = 4, memo[cur - coin] + 1 等于 memo[1]+1,也就是2，这说明可以用2个1组成2 memo[2] = 2
                    // 再算硬币2，memo[2] = 2, memo[cur - coin] + 1 等于 memo[0]+1,也就是1，这说明可以用1个2组成2 memo[2] = 1
                    // 硬币5进不来，最终 memo[2]=1;
                    memo[cur] = Math.min(memo[cur], memo[cur - coin] + 1);
                }
            }

        }
        return memo[amount] == (amount + 1) ? -1 : memo[amount];
    }

}


